package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.sun.org.apache.xml.internal.security.keys.content.RetrievalMethod;
import com.sun.xml.internal.messaging.saaj.packaging.mime.Header;

import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;
import util.datastructure.ListNode;

/*
 * 
原题　
	Given a singly linked list, determine if it is a palindrome.
	
	Follow up:
	Could you do it in O(n) time and O(1) space?
题目大意
	给条单链表，判断是否为回文链表
解题思路
	
 * @Date 2017-09-26 00：22
 */
public class _234_Palindrome_Linked_List {
    /**
     * 得到链表总长度
     * @param head
     * @return
     */
    public int getListLength(ListNode head) {
    	int total = 0;
    	ListNode p = head;
    	while (p != null) {
    		total++;
    		p = p.next;
    	}
    	return total;
    }
    
    /**
     * 判断是否是回文
     * TODO:超时异常 
     * @param head
     * @return
     */
//	public boolean isPalindrome(ListNode head) {
//		if (head == null)	return true;
//		int N = getListLength(head);
//		if (N==0 || N==1)	return true;
//		ListNode p = head;
//		int l = 1, r = N;
//		while (l < r) {
//			if (find(head, l).val != find(head, r).val) {
//				return false;
//			}
//			l++;
//			r--;
//		}
//
//		return true;
//	}
    
    /**
     * 思路：将链表反转：看下反转后的链表是否与原链表相等
     * @param head
     * @return
     */
	public boolean isPalindrome(ListNode head) {
		if (getListLength(head)==0 || getListLength(head)==1) 	return true;
		ListNode reverseList = newReverseList(head);
		ListNode p = head, q = reverseList;
		
		ListNode.traverse("正>>", head);
		ListNode.traverse("负>>", reverseList);
		while (p!=null && q!=null) {
			if (p.val != q.val) {
				return false;
			}
			p = p.next;
			q = q.next;
		}
		return true;
	}

	
	/**
	 * 反转链表 
	 * 	：思路：头插法建立一个反转后的链表、将其余原链表比对是否一样
	 * @param head
	 * @param startIndex
	 * @return
	 */
	public ListNode newReverseList(ListNode head) {

		ListNode p = head;
		ListNode rHead = null;
		
		while (p != null) {
			//头插法
			ListNode newNode = new ListNode(p.val);
			newNode.next = rHead;
			rHead = newNode;
			
			p = p.next;
		}
		ListNode.traverse("新反>>", rHead);
		return rHead;
	}
	
	/**
	 * 发现第num个节点
	 * @param head
	 * @param num
	 * @return
	 */
	public ListNode find(ListNode head, int num) {
    	int count = 1;
    	ListNode p = head;
    	while (count<num) {
    		count ++;
    		p = p.next;
    	}
    	return p;
	}
	
	public static void main(String[] args) {
		_234_Palindrome_Linked_List obj = new _234_Palindrome_Linked_List();
		System.out.println(obj.isPalindrome(ListNode.newPalindromeLinkList()));
	}
}
